//
// Created by REEJI2219 on 2024-08-15.
//
#include <iostream>
using namespace std;

class String {
    char *string;
    int length;
    int max_length;

public:
    String() {
        length = 0;
        max_length = 200;
        string = new char[max_length + 1];
        string[0] = '\0';
    }

    String(char *string) {
        length = 0;
        max_length = 200;
        this->string = new char[max_length];
        char str = *string;
        int i = 0;
        while (str != '\0') {
            *(this->string + i) = str;
            i++;
            if (i >= max_length) {
                max_length = i;
                string[i] = '\0';
                return;
            }
            str = *(string + i);
        }
        length = i;
        this->string[length] = '\0';
    }

    bool getStaring(char *string) {
        if (string != nullptr) {
            *string = *this->string;
            return true;
        }
        return false;
    }

    void printChar() {
        for (int i = 0; i < length; i++) {
            printf("%c", *(this->string + i));
        }
        printf("\n");
    }

    bool append(String *string) {
        if (this->length == max_length) {
            return true;
        }
        char str = *(string->string);
        int i = 0;
        while (str != '\0') {
            *(this->string + this->length + i) = str;
            i++;
            if (this->length + i == max_length) {
                this->length = max_length;
                this->string[this->length] = '\0';
                return true;
            }
            str = *(string->string + i);
        }
        this->length = this->length + i;
        this->string[this->length] = '\0';
    }

    int getLength() {
        return this->length;
    }

    bool subString(int start, int end, String *string) {
        if (start < 0 || end > this->length || end > max_length) {
            return false;
        }
        int i = 0;
        char str = this->string[start + i];
        while (str != '\0' && i + start < end) {
            string->string[i] = str;
            i++;
            str = this->string[start + i];
        }
        string->length = end - start;
        string->string[string->length] = '\0';
        return true;
    }

    /**
     * 字符串按照字典顺序比较
     * -1 我小，我靠前
     * 0 相等
     * 1 我大，我靠后
     * @param string
     * @return
     */
    int compore(String *string) {
        int i = 0;
        char str1 = this->string[i];
        char str2 = string->string[i];
        //相同范围内,比较
        while (str1 == str2 && i < this->length && i < string->length) {
            str1 = this->string[i];
            str2 = string->string[i];
            i++;
        }
        //出现不一致清空，也可能是某个字符串结束了,也可能都结束了
        if (str1 != str2) {
            return str1 < str2 ? -1 : 1;
        }
        //当前结束了
        if (i == this->length) {
            if (i < string->length) {
                //我结束了，但是另外的没结束，我小
                return -1;
            } else {
                return 0;
            }
        }
        if (i == string->length) {
            if (i < this->length) {
                //另外结束了，我没结束，我大
                return 1;
            } else {
                //都结束了，并且相等
                return 0;
            }
        }
        //我俩相等
        return 0;
    }

    int indexOf(String *str) {
        for (int i = 0; i < this->length - str->length + 1; i++) {
            String *subStr=new String();
            this->subString(i, str->length+i, subStr);
            if(str->compore(subStr)==0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 普速算法 暴力破解
     * 时间复杂度 o(M*N)
     * @param str
     * @return
     */
    int indexOf2(String *str) {
        for (int i = 0; i < this->length - str->length + 1; i++) {
            int star=i;
            for(int j=0;j<str->length;j++) {
                if(this->string[star]!=str->string[j]) {
                    break;
                }
                star++;
            }
            if(star-i==str->length) {
                return i;
            }
        }
        return -1;
    }
    int* buildNext() {
        int *next=new int[this->length];
        next[0]=0;
        //遍历每个子串
        for (int i=1;i<this->length;i++) {
            //获取每个子串的最大重复子串长度
            //此时i为结束位置
            for(int j=0;j<i;j++) {
                //右边开始位置
                int rightIndex = i-j;
                //左边开始位置
                int leftIndex=0;
                bool compareSuccess=true;
                while (rightIndex<=i) {
                    if(this->string[leftIndex]==this->string[rightIndex]) {
                        leftIndex++;
                        rightIndex++;
                    }else {
                        compareSuccess=false;
                        break;
                    }
                }
                if(compareSuccess) {
                    next[i]=leftIndex;
                }
            }
        }
        for (int i=0;i<this->length;i++) {
            printf("%d ",next[i]);
        }
        printf("\n");
        return next;
    }

    /**
    * 当 i 和 j 匹配时，i 和 j 同时右移一格
    * 当 i 和 j 不匹配时，如果 j 不在字符串开头（位置 0），就回退到上一个能匹配到的位置
    * 当 i 和 j 不匹配时，如果 j 在字符串开头（位置 0），那么 i 就右移一格
     * @return
     */
    int *buildNext2() {
        int *next = new int[this->length];
        int i=1;
        int j=0;
        next[0]=0;
        while (i<this->length) {
            if(this->string[i]==this->string[j]) {
                next[i]=j+1;
                i++;
                j++;
            }else {
                if(j>0) {
                    j=next[j-i];
                }else {
                    next[i]=0;//此处不写也行，因为int数组默认值为0
                    i++;
                }
            }
        }
    }


    /**
     * https://www.xdull.cn/kmp.html
     *
     * @param str
     * @return
     */
    int KMPIndex(String *str) {
        int *next = str->buildNext2();
        int j=0;
        int i=0;
        while (i<this->length) {
            //两者数据相等，遍历下一个
            if(this->string[i]==str->string[j]) {
                j++;
                i++;
            }else {
              if(j>0) {//当前匹配失败
                  /**
                   *j-1前面是匹配成功的，就是这两部分子串全部相同
                   *回退导next[j-1]继续匹配。
                   *因为j-1是匹配成功的。假设 n=j-1。n代码了前缀匹配成功的最长长度，也就复用了前面使用的数据
                   *n存的是长度，有一个时，则从第二个开始继续比较，a[1]其实是第二个。再继续向下比较一次
                   *此处为何不i+1，因为还要再比较一次，万一跟前面的几个对上了。比如
                   *str1 abababc
                   *str2 ababc
                   *a!=c时 next[3]=2
                   *复用了ab。此时 str2[2]继续匹str1[4],相等，继续，匹配完成
                   *
                   */
                  j=next[j-1];
              }else {
                  //如何为0，说明没有可用的了，i+1，重新开始吧
                  i++;
              }
            }
            //str遍历结束
            if(j==str->length) {
                return i-j;
            }
        }
        return -1;
    }
};

// int main(int argc, char *argv[]) {
//     String *str = new String("hello12");
//     String *str2 = new String("lo");
//     // cout<<str->getLength()<<endl;
//     // cout<<str2->getLength()<<endl;
//     // str->append(str2);
//     // str->printChar();
//     // cout<<str->getLength()<<endl;
//     // String *str3 = new String();
//     // str->subString(2,12,str3);
//     // str3->printChar();
//     // cout << str->compore(str2) << endl;
//     cout << str->indexOf(str2)<< endl;
//     cout << str->indexOf2(str2)<< endl;
//     // int *next=str2->buildNext();
//     cout << str->KMPIndex(str2)<< endl;
// }
